﻿// 1003train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <queue>

using namespace std;

/*
 请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。
为了保证输出的二又树中序遍历结果统一，增加以下限制：
二叉树节点中，左节点权值小于等于右节点权值，根节点权值为左右节点权值之和。
当左右节点权值相同时，左子树高度高度小于等于右子树

输入描述
第一行输入为数组长度，记为N，1<=N<=1000
第二行输入无序数值数组，以空格分割，数值均大于等于1，小于100000

输出描述
输出一个哈夫曼树的中序遍历的数组，数值间以空格分割

示例
输入
5
5 15 40 30 10
输出
40 100 30 60 15 30 5 15 10
 */
class Solution01
{
public:
    struct TreeNode
    {
        int val, height;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val, int height, TreeNode* left, TreeNode* right) :
            val(val), height(height), left(left), right(right) {};
    };

    TreeNode* buildTree(vector<int>& num_vec)
    {
        vector<TreeNode*>sort_v;
        for (auto&num:num_vec)
        {
            sort_v.push_back(new TreeNode(num, 0, nullptr, nullptr));
        }
        while (sort_v.size()>1)
        {
            sort(sort_v.begin(), sort_v.end(), [](TreeNode*node_1,TreeNode*node_2)
                {
                    if (node_1->val == node_2->val)
                        return node_1->height > node_2->height;
                    return node_1->val > node_2->val;
                });

            //左节点权值小于等于右节点权值
            //左子树高度高度小于等于右子树
            TreeNode* left = sort_v.back(); sort_v.pop_back();
            TreeNode* right = sort_v.back(); sort_v.pop_back();

            int new_val = left->val + right->val;
            int new_h = max(left->height, right->height) + 1;

            sort_v.push_back(new TreeNode(new_val, new_h, left, right));

	        //while---
        }
        return sort_v[0];
	    //buildTree
    }

    void inorder(TreeNode* node, vector<int>&result)
    {
        if (node == nullptr) return;

        inorder(node->left, result);
        result.push_back(node->val);
        inorder(node->right, result);
	    //inorder
    }

    Solution01(vector<int>&num_vec)
    {
        TreeNode* root = buildTree(num_vec);
        vector<int>result;
        inorder(root, result);

        for (auto&num:result)
        {
            cout << num << ' ';
        }
	    //Solution01
    }
};


/*
2行整数，第1行表示二叉树的中序遍历，第2行表示二叉树的前序遍历
请由该二叉树生成一个新的二叉树，它满足其树中的每个节点将包含原始树中的左子树和右子树的和。
输入
8 12 -3 6 -10 9 -7
-3 12 8 6 9 -10 -7
输出
0 8 18 -8 0 -17 0

1行整数，表示求和树的中序遍历，以空格分割
 */
class Solution02
{
public:
    struct TreeNode
    {
        int val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val, TreeNode* left, TreeNode* right) :val(val), left(left), right(right) {};
    };

    void insertNode(TreeNode*root, TreeNode*node)
    {
        while (root!=node)
        {
            if (inorder_map.at(node->val)<inorder_map.at(root->val))
            {
	            if (root->left==nullptr)
	            {
                    root->left = node;
                    break;
	            }
                root = root->left;
            }
            else
            {
                if (root->right==nullptr)
                {
                    root->right = node;
                    break;
                }
                root = root->right;
            }
	        //while---
        }
        //
    }

    TreeNode* buildNew(TreeNode* node)
    {
        int old_left_val = 0;
        int new_left_val = 0;
        TreeNode* new_left = nullptr;
        if (node->left!=nullptr)
        {
            old_left_val = node->left->val;
            new_left = buildNew(node->left);
            new_left_val = new_left->val;
        }

        int old_right_val = 0;
        int new_right_val = 0;
        TreeNode* new_right = nullptr;
        if (node->right!=nullptr)
        {
            old_right_val = node->right->val;
            new_right = buildNew(node->right);
            new_right_val = new_right->val;
        }

        int node_val = old_left_val + new_left_val + old_right_val + new_right_val;

        return new TreeNode(node_val, new_left, new_right);
	    //buildNew
    }

    void inorder(TreeNode*node, vector<int>&result)
    {
        if (node == nullptr) return;
        inorder(node->left, result);
        result.push_back(node->val);
        inorder(node->right, result);
	    //inorder
    }


    Solution02(vector<int>&inorder_v, vector<int>&preorder_v)
    {
        int inorder_size = inorder_v.size();
        for (int i=0; i<inorder_size; i++)
        {
            inorder_map[inorder_v[i]] = i;
        }

        TreeNode* root = new TreeNode(preorder_v[0], nullptr, nullptr);
        int v_size = preorder_v.size();
    	for (int i=1;i<v_size; i++)
    	{
            TreeNode* node = new TreeNode(preorder_v[i], nullptr, nullptr);
            insertNode(root, node);
    	}

        TreeNode* new_root = buildNew(root);
        vector<int>result;
        inorder(new_root, result);

        for (auto&num:result)
        {
            cout << num << ' ';
        }
	    //Solution02
    }
private:
    unordered_map<int, int>inorder_map;
};


/*
 小王手里有点闲钱，想着做点卖水果的小买卖
 给出两个数组 m、n，用 m[i]代表第 i 个水果的成本价，n[i]代表第 i 个水果能卖出的价钱，
 假如现在有本钱 k，试问最后最多能赚多少钱？
说明：
1 每种水果只需买一次，只能卖一次
2 数组 m、n 大小不超过 50
3 数组元素为正整数，不超过 1000
输入描述：
1 数组 m、n
2 本钱 k
备注：
1 首行输入逗号分隔的数组 m 的元素值
2 第二行输入逗号分隔的数组 n 的元素值
3 第三行输入本钱
输出描述：
最多能赚取多少钱。
示例 1
输入
4,2,6,4
5,3,8,7
15
输出
22
 */
class Solution03
{
public:
    struct Node
    {
        int buy, sale;
        double para;
        Node() = default;
        Node(int buy, int sale, double para) :buy(buy), sale(sale), para(para) {};
    };

    Solution03(vector<int>&buy_vec,vector<int>&sale_vec,int money)
    {
        int v_size = buy_vec.size();
        vector<Node>benefit_vec;
        for (int i=0; i<v_size; i++)
        {
            int buy_item = buy_vec[i];
            int sale_item = sale_vec[i];
            int val = sale_item - buy_item;
            double para = double(val) / double(buy_item);

            benefit_vec.push_back(Node(buy_item, sale_item,para));
        }
        sort(benefit_vec.begin(), benefit_vec.end(), [](Node&node_1,Node&node_2)
            {
                return node_1.para > node_2.para;
            });


        vector<bool>checked(v_size,false);
        while (true)
        {
            bool is_buy = false;
            for (int i=0; i<v_size; i++)
            {
                Node item = benefit_vec[i];
	            if (money>=item.buy && !checked[i])
	            {
                    money -= item.buy;
                    money += item.sale;
                    checked[i] = true;
                    is_buy = true;
	            }
                //for---
            }

            if (!is_buy) break;
            //while---
        }

        cout << money;
	    //Solution03
    }
};

/*
 给你一个整数数组 desk 表示当前座位的占座情况，
 由若干 0 和 1 组成，其中 0 表示没有占位，1 表示占位
 在不改变原有座位秩序情况下，还能安排坐几个人？
输入
第一行是个子数组表示作为占座情况，由若干 0 和 1 组成，其中 0 表示没有占位，1 表示占位
输出
输出数值表示还能坐几个人

输入
0,0,0,0,0
输出
3
 */
class Solution04
{
public:
    Solution04(vector<int>&num_vec)
    {
        int v_size = num_vec.size();
        int index = 0;

        int result = 0;
        while (index<v_size)
        {
            if (index + 1<v_size && num_vec[index+1]==1)
            {
                index += 3;
                continue;
            }
            if (num_vec[index]==1)
            {
                index += 2;
                continue;
            }

            if (num_vec[index]==0)
            {
                result += 1;
                index += 2;
            }
            
	        //while
        }
        cout << result;
	    //
    }
};


int main()
{
	{
        string num_str;
        getline(cin, num_str);
        stringstream oh_sstream(num_str);
        string token;
        vector<int>num_vec;
        while (getline(oh_sstream,token,','))
        {
            num_vec.push_back(stoi(token));
        }

        Solution04 solu(num_vec);

        return 0;
	}
	{
        string buy_str;
        vector<int>buy_vec;
        getline(cin, buy_str);
        stringstream buy_sstream(buy_str);
        string token;
        while (getline(buy_sstream,token,','))
        {
            buy_vec.push_back(stoi(token));
        }

        vector<int>sale_vec;
        string sale_str;
        getline(cin, sale_str);
        stringstream sale_sstream(sale_str);
        while (getline(sale_sstream,token,','))
        {
            sale_vec.push_back(stoi(token));
        }

        string money_str;
        getline(cin, money_str);
        int money = stoi(money_str);

        Solution03 solu(buy_vec, sale_vec, money);

        return 0;
	}
	{
        //8 12 -3 6 -10 9 -7
        //-3 12 8 6 9 - 10 - 7
        vector<int>inorder_vec;
        string inorder_str;
        getline(cin, inorder_str);
        stringstream inorder_sstream(inorder_str);
        string token;
        while (inorder_sstream>>token)
        {
            inorder_vec.push_back(stoi(token));
        }

        vector<int>preorder_vec;
        string preorder_str;
        getline(cin, preorder_str);
        stringstream preorder_sstream(preorder_str);
        while (preorder_sstream>>token)
        {
            preorder_vec.push_back(stoi(token));
        }

        Solution02 solu(inorder_vec, preorder_vec);

        return 0;
	}
    //5
    //5 15 40 30 10
    int v_size;
    cin >> v_size;
    vector<int>num_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> num_vec[i];
    }
    Solution01 solu(num_vec);
    return 0;
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
